/*最小高度=ceiling(最大高度/2)
* 
*/
class Solution {
public:
    int findLongestNode(int cur, vector<int> &parent, vector<vector<int>> &adj)
    {
        int n=adj.size();
        queue<int> q;
        vector<bool> vis(n);
        q.emplace(cur);
        vis[cur]=true;
        int ret=-1;

        while(!q.empty())
        {
            int u=q.front(); q.pop();
            ret=u;
            for(auto &v:adj[u]) {
                if(!vis[v]) {
                    vis[v]=true;
                    parent[v]=u;
                    q.emplace(v);
                }
            }
        }
        return ret;

    }

    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n==1) return {0};
        vector<vector<int>> adj(n); //无向图 邻接表
        for(auto &edge:edges) {
            adj[edge[0]].emplace_back(edge[1]);
            adj[edge[1]].emplace_back(edge[0]);
        }

        vector<int> parent(n, -1);

        int x=findLongestNode(0, parent, adj); //找到与节点0最远的节点
        int y=findLongestNode(x, parent, adj); //找到与节点x最远的节点
        vector<int> path;
        parent[x]=-1; //令x为根节点
        while(y!=-1){
            path.emplace_back(y);
            y=parent[y];
        }

        int m=path.size();
        if(m%2==0) return {path[m/2-1], path[m/2]};
        else return {path[m/2]};
    }
};